翻訳と辞書 Words near each other ・ Quadrula tuberosa ・ Quadrumana ・ Quadratic integrate and fire ・ Quadratic irrational ・ Quadratic Jordan algebra ・ Quadratic Lie algebra ・ Quadratic mean diameter ・ Quadratic pair ・ Quadratic probing ・ Quadratic programming ・ Quadratic reciprocity ・ Quadratic residue ・ Quadratic residue code ・ Quadratic residuosity problem ・ Quadratic set ・ Quadratic sieve ・ Quadratic transformation ・ Quadratic unconstrained binary optimization ・ Quadratic variation ・ Quadratic-linear algebra ・ Quadratically closed field ・ Quadratically constrained quadratic program ・ Quadratics ・ Quadratini ・ Quadratino ・ Quadrato di Villafranca ・ Quadratojugal bone ・ Quadratrix ・ Quadratrix of Hippias ・ Quadratur des Kreises Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Quadratic sieve ： ウィキペディア英語版 Quadratic sieve The quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second fastest method known (after the general number field sieve). It is still the fastest for integers under 100 decimal digits or so, and is considerably simpler than the number field sieve. It is a general-purpose factorization algorithm, meaning that its running time depends solely on the size of the integer to be factored, and not on special structure or properties. It was invented by Carl Pomerance in 1981 as an improvement to Schroeppel's linear sieve.〔Carl Pomerance, Analysis and Comparison of Some Integer Factoring Algorithms, in Computational Methods in Number Theory, Part I, H.W. Lenstra, Jr. and R. Tijdeman, eds., Math. Centre Tract 154, Amsterdam, 1982, pp 89-139.〕 ==Basic aim== The algorithm attempts to set up a congruence of squares modulo ''n'' (the integer to be factorized), which often leads to a factorization of ''n''. The algorithm works in two phases: the ''data collection'' phase, where it collects information that may lead to a congruence of squares; and the ''data processing'' phase, where it puts all the data it has collected into a matrix and solves it to obtain a congruence of squares. The data collection phase can be easily parallelized to many processors, but the data processing phase requires large amounts of memory, and is difficult to parallelize efficiently over many nodes or if the processing nodes do not each have enough memory to store the whole matrix. The block Wiedemann algorithm can be used in the case of a few systems each capable of holding the matrix. The naive approach to finding a congruence of squares is to pick a random number, square it, and hope the least non-negative remainder modulo ''n'' is a perfect square (in the integers). For example, 802 mod 5959 is 441, which is 212. This approach finds a congruence of squares only rarely for large ''n'', but when it does find one, more often than not, the congruence is nontrivial and the factorization is complete. This is roughly the basis of Fermat's factorization method. The quadratic sieve is a modification of Dixon's factorization method. The general running time required for the quadratic sieve (to factor an integer ''n'') is :$e^\{(1\; +\; o(1))\backslash sqrt\{\backslash ln\; n\; \backslash ln\backslash ln\; n\}\}\; =L\_n\backslash left()$ in the L-notation. The constant ''e'' is the base of the natural logarithm. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Quadratic sieve」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.